package leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import list.LinkedListCreate;
import list.ListNode;

public class ReorderList {

	public static void main(String[] args) {
		ReorderList object = new ReorderList();
		int[] nums = {1, 2, 3};
		ListNode head = LinkedListCreate.createList(nums);
		object.reorderList(head);
		LinkedListCreate.printList(head);
	}
	
	
	public void reorderList(ListNode head) {
		if (head == null) {
			return;
		}
		Stack<ListNode> stack = new Stack<>();
		Queue<ListNode> queue = new LinkedList<>();
		ListNode node = head;
		int length = 0;
		while (node != null) {
			node = node.next;
			length++;
		}
		System.out.println(length);
		node = head;
		int curIndex = 0;
		int queueLength = (length + 1) / 2;
		while (node != null) {
			if (curIndex < queueLength) {
				queue.add(node);
				curIndex++;
			} else {
				stack.add(node);
			}
			node = node.next;
		}
		System.out.println("size：" + queue.size() + "  " + stack.size());
		ListNode queueNode = null;
		ListNode stackNode = null;
		while (!stack.isEmpty()) {
			stackNode = stack.pop();
			queueNode = queue.poll();
			stackNode.next = queue.peek();
			queueNode.next = stackNode;
		}
		if(!queue.isEmpty()){
			queue.poll().next = null;
		}
	}
}
